package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/20 9:09
 * @description :8道
*        人生几回春？
*            2021.10.20
 *
 */
public class t20211020 {

    //21.合并两个有序链表
    static public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 != null && l2 == null) {
            return l1;
        } else if (l1 == null && l2 != null) {
            return l2;
        }

        ListNode dummy = new ListNode(-1);//dummy节点，用于最终返回
        ListNode temp = dummy;

        while (l1 != null || l2 != null) {

            if (l1 != null && l2 != null) {
                if (l2.val <= l1.val) {
                    dummy.next = l2;
                    dummy = dummy.next;
                    l2 = l2.next;
                    continue;

                } else {
                    dummy.next = l1;
                    dummy = dummy.next;
                    l1 = l1.next;
                    continue;
                }

            }

            if (l1 == null) {
                dummy.next = l2;
                dummy = dummy.next;
                l2 = l2.next;
                continue;

            }
            if (l2 == null) {
                dummy.next = l1;
                dummy = dummy.next;
                l1 = l1.next;
                continue;
            }

        }

        return temp.next;
    }

    //206. 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        ListNode temp = head;


        while (true) {

            if (temp.next == null) {
                ListNode buffer = dummy.next;
                dummy.next = temp;
                temp.next = buffer;
                break;
            }
            ListNode buffer = dummy.next;
            dummy.next = temp;
            ListNode next = temp.next;
            temp.next = buffer;

            temp = next;


        }

        return dummy.next;

    }

    //面试题04.06 后继者
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) {
            return null;
        }

        if (root.val == p.val) {//说明p的中序后后继一定在root右边第一个
            TreeNode node = root.right;

            while (node != null && node.left != null) {
                node = node.left;
            }

            return node;

        }

        if (p.val < root.val) {//说明p的中序后序一定在root左边或者就是root

            TreeNode node = inorderSuccessor(root.left, p);
            return node == null ? root : node;

        } else {

            return inorderSuccessor(root.right, p);
        }


    }

    //面试题04.08 首个共同祖先
    static public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        /*
            这题分为三种情况：
            1.p，q分别在左子树，右子树上
            2.p.q在同一棵树上（左/右
            3.p.q其中又一个是根节点
         */

        if (root == p || root == q) {
            return root;
        }


        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        }

        return left == null ? right : left;
    }

    //面试题04.09 二叉搜索树序列 TODO
    public List<List<Integer>> BSTSequences(TreeNode root) {

        return null;
    }

    private List<Integer> getDfs(TreeNode root, int first) {
        if (root == null) {
            return null;
        }

        if (root.left == null && root.right == null) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(first);
            list.add(root.val);
            return list;
        }

        List<Integer> list1 = getDfs(root.left, first);//9,4
        List<Integer> list2 = getDfs(root.right, first);//9,7

        list1.addAll(list2);
        list1.remove(0);

        return list1;


    }


    //面试题04.10 检查子树
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2 == null;
        }

        return isSame(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    private boolean isSame(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }


        return t1.val == t2.val && isSame(t1.left, t2.left) && isSame(t1.right, t2.right);

    }

    //面试题04.12 求和路径  自顶而下
    int res = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        deep(root,new ArrayList<Integer>(),sum);
        return res;

    }

    private void deep(TreeNode root, List<Integer> list, int target) {
        if (root == null) {
            return;
        }

        int curSum = 0;
        list.add(root.val);//list存放路径节点

        for (int i = list.size() - 1; i >= 0; i--) {
            curSum += list.get(i);
            if (curSum == target) {
                res++;
            }
        }

        deep(root.left, list, target);
        deep(root.right, list, target);

        list.remove(list.size() - 1);


    }


    //100.相同的树
    static public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);

        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);

        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(8);

        root.left = node1;
        root.right = node2;

        node3.left = node4;
        node3.right = node5;

        ArrayList<Object> lis = new ArrayList<>();

    }

}

class ListNodeQ {
    int val;
    ListNode next;

    ListNodeQ() {
    }

    ListNodeQ(int val) {
        this.val = val;
    }

    ListNodeQ(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

